{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "google",
   "metadata": {},
   "source": [
    "##### Copyright 2023 Google LLC."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "apache",
   "metadata": {},
   "source": [
    "Licensed under the Apache License, Version 2.0 (the \"License\");\n",
    "you may not use this file except in compliance with the License.\n",
    "You may obtain a copy of the License at\n",
    "\n",
    "    http://www.apache.org/licenses/LICENSE-2.0\n",
    "\n",
    "Unless required by applicable law or agreed to in writing, software\n",
    "distributed under the License is distributed on an \"AS IS\" BASIS,\n",
    "WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\n",
    "See the License for the specific language governing permissions and\n",
    "limitations under the License.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "basename",
   "metadata": {},
   "source": [
    "# flexible_job_shop_sat"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "link",
   "metadata": {},
   "source": [
    "<table align=\"left\">\n",
    "<td>\n",
    "<a href=\"https://colab.research.google.com/github/google/or-tools/blob/main/examples/notebook/examples/flexible_job_shop_sat.ipynb\"><img src=\"https://raw.githubusercontent.com/google/or-tools/main/tools/colab_32px.png\"/>Run in Google Colab</a>\n",
    "</td>\n",
    "<td>\n",
    "<a href=\"https://github.com/google/or-tools/blob/main/examples/python/flexible_job_shop_sat.py\"><img src=\"https://raw.githubusercontent.com/google/or-tools/main/tools/github_32px.png\"/>View source on GitHub</a>\n",
    "</td>\n",
    "</table>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "doc",
   "metadata": {},
   "source": [
    "First, you must install [ortools](https://pypi.org/project/ortools/) package in this colab."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "install",
   "metadata": {},
   "outputs": [],
   "source": [
    "%pip install ortools"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "description",
   "metadata": {},
   "source": [
    "\n",
    "Solves a flexible jobshop problems with the CP-SAT solver.\n",
    "\n",
    "A jobshop is a standard scheduling problem when you must sequence a\n",
    "series of task_types on a set of machines. Each job contains one task_type per\n",
    "machine. The order of execution and the length of each job on each\n",
    "machine is task_type dependent.\n",
    "\n",
    "The objective is to minimize the maximum completion time of all\n",
    "jobs. This is called the makespan.\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "code",
   "metadata": {},
   "outputs": [],
   "source": [
    "import collections\n",
    "\n",
    "from ortools.sat.python import cp_model\n",
    "\n",
    "\n",
    "class SolutionPrinter(cp_model.CpSolverSolutionCallback):\n",
    "    \"\"\"Print intermediate solutions.\"\"\"\n",
    "\n",
    "    def __init__(self):\n",
    "        cp_model.CpSolverSolutionCallback.__init__(self)\n",
    "        self.__solution_count = 0\n",
    "\n",
    "    def on_solution_callback(self):\n",
    "        \"\"\"Called at each new solution.\"\"\"\n",
    "        print(\n",
    "            \"Solution %i, time = %f s, objective = %i\"\n",
    "            % (self.__solution_count, self.WallTime(), self.ObjectiveValue())\n",
    "        )\n",
    "        self.__solution_count += 1\n",
    "\n",
    "\n",
    "def flexible_jobshop():\n",
    "    \"\"\"Solve a small flexible jobshop problem.\"\"\"\n",
    "    # Data part.\n",
    "    jobs = [  # task = (processing_time, machine_id)\n",
    "        [  # Job 0\n",
    "            [(3, 0), (1, 1), (5, 2)],  # task 0 with 3 alternatives\n",
    "            [(2, 0), (4, 1), (6, 2)],  # task 1 with 3 alternatives\n",
    "            [(2, 0), (3, 1), (1, 2)],  # task 2 with 3 alternatives\n",
    "        ],\n",
    "        [  # Job 1\n",
    "            [(2, 0), (3, 1), (4, 2)],\n",
    "            [(1, 0), (5, 1), (4, 2)],\n",
    "            [(2, 0), (1, 1), (4, 2)],\n",
    "        ],\n",
    "        [  # Job 2\n",
    "            [(2, 0), (1, 1), (4, 2)],\n",
    "            [(2, 0), (3, 1), (4, 2)],\n",
    "            [(3, 0), (1, 1), (5, 2)],\n",
    "        ],\n",
    "    ]\n",
    "\n",
    "    num_jobs = len(jobs)\n",
    "    all_jobs = range(num_jobs)\n",
    "\n",
    "    num_machines = 3\n",
    "    all_machines = range(num_machines)\n",
    "\n",
    "    # Model the flexible jobshop problem.\n",
    "    model = cp_model.CpModel()\n",
    "\n",
    "    horizon = 0\n",
    "    for job in jobs:\n",
    "        for task in job:\n",
    "            max_task_duration = 0\n",
    "            for alternative in task:\n",
    "                max_task_duration = max(max_task_duration, alternative[0])\n",
    "            horizon += max_task_duration\n",
    "\n",
    "    print(\"Horizon = %i\" % horizon)\n",
    "\n",
    "    # Global storage of variables.\n",
    "    intervals_per_resources = collections.defaultdict(list)\n",
    "    starts = {}  # indexed by (job_id, task_id).\n",
    "    presences = {}  # indexed by (job_id, task_id, alt_id).\n",
    "    job_ends = []\n",
    "\n",
    "    # Scan the jobs and create the relevant variables and intervals.\n",
    "    for job_id in all_jobs:\n",
    "        job = jobs[job_id]\n",
    "        num_tasks = len(job)\n",
    "        previous_end = None\n",
    "        for task_id in range(num_tasks):\n",
    "            task = job[task_id]\n",
    "\n",
    "            min_duration = task[0][0]\n",
    "            max_duration = task[0][0]\n",
    "\n",
    "            num_alternatives = len(task)\n",
    "            all_alternatives = range(num_alternatives)\n",
    "\n",
    "            for alt_id in range(1, num_alternatives):\n",
    "                alt_duration = task[alt_id][0]\n",
    "                min_duration = min(min_duration, alt_duration)\n",
    "                max_duration = max(max_duration, alt_duration)\n",
    "\n",
    "            # Create main interval for the task.\n",
    "            suffix_name = \"_j%i_t%i\" % (job_id, task_id)\n",
    "            start = model.NewIntVar(0, horizon, \"start\" + suffix_name)\n",
    "            duration = model.NewIntVar(\n",
    "                min_duration, max_duration, \"duration\" + suffix_name\n",
    "            )\n",
    "            end = model.NewIntVar(0, horizon, \"end\" + suffix_name)\n",
    "            interval = model.NewIntervalVar(\n",
    "                start, duration, end, \"interval\" + suffix_name\n",
    "            )\n",
    "\n",
    "            # Store the start for the solution.\n",
    "            starts[(job_id, task_id)] = start\n",
    "\n",
    "            # Add precedence with previous task in the same job.\n",
    "            if previous_end is not None:\n",
    "                model.Add(start >= previous_end)\n",
    "            previous_end = end\n",
    "\n",
    "            # Create alternative intervals.\n",
    "            if num_alternatives > 1:\n",
    "                l_presences = []\n",
    "                for alt_id in all_alternatives:\n",
    "                    alt_suffix = \"_j%i_t%i_a%i\" % (job_id, task_id, alt_id)\n",
    "                    l_presence = model.NewBoolVar(\"presence\" + alt_suffix)\n",
    "                    l_start = model.NewIntVar(0, horizon, \"start\" + alt_suffix)\n",
    "                    l_duration = task[alt_id][0]\n",
    "                    l_end = model.NewIntVar(0, horizon, \"end\" + alt_suffix)\n",
    "                    l_interval = model.NewOptionalIntervalVar(\n",
    "                        l_start, l_duration, l_end, l_presence, \"interval\" + alt_suffix\n",
    "                    )\n",
    "                    l_presences.append(l_presence)\n",
    "\n",
    "                    # Link the primary/global variables with the local ones.\n",
    "                    model.Add(start == l_start).OnlyEnforceIf(l_presence)\n",
    "                    model.Add(duration == l_duration).OnlyEnforceIf(l_presence)\n",
    "                    model.Add(end == l_end).OnlyEnforceIf(l_presence)\n",
    "\n",
    "                    # Add the local interval to the right machine.\n",
    "                    intervals_per_resources[task[alt_id][1]].append(l_interval)\n",
    "\n",
    "                    # Store the presences for the solution.\n",
    "                    presences[(job_id, task_id, alt_id)] = l_presence\n",
    "\n",
    "                # Select exactly one presence variable.\n",
    "                model.AddExactlyOne(l_presences)\n",
    "            else:\n",
    "                intervals_per_resources[task[0][1]].append(interval)\n",
    "                presences[(job_id, task_id, 0)] = model.NewConstant(1)\n",
    "\n",
    "        job_ends.append(previous_end)\n",
    "\n",
    "    # Create machines constraints.\n",
    "    for machine_id in all_machines:\n",
    "        intervals = intervals_per_resources[machine_id]\n",
    "        if len(intervals) > 1:\n",
    "            model.AddNoOverlap(intervals)\n",
    "\n",
    "    # Makespan objective\n",
    "    makespan = model.NewIntVar(0, horizon, \"makespan\")\n",
    "    model.AddMaxEquality(makespan, job_ends)\n",
    "    model.Minimize(makespan)\n",
    "\n",
    "    # Solve model.\n",
    "    solver = cp_model.CpSolver()\n",
    "    solution_printer = SolutionPrinter()\n",
    "    status = solver.Solve(model, solution_printer)\n",
    "\n",
    "    # Print final solution.\n",
    "    for job_id in all_jobs:\n",
    "        print(\"Job %i:\" % job_id)\n",
    "        for task_id in range(len(jobs[job_id])):\n",
    "            start_value = solver.Value(starts[(job_id, task_id)])\n",
    "            machine = -1\n",
    "            duration = -1\n",
    "            selected = -1\n",
    "            for alt_id in range(len(jobs[job_id][task_id])):\n",
    "                if solver.Value(presences[(job_id, task_id, alt_id)]):\n",
    "                    duration = jobs[job_id][task_id][alt_id][0]\n",
    "                    machine = jobs[job_id][task_id][alt_id][1]\n",
    "                    selected = alt_id\n",
    "            print(\n",
    "                \"  task_%i_%i starts at %i (alt %i, machine %i, duration %i)\"\n",
    "                % (job_id, task_id, start_value, selected, machine, duration)\n",
    "            )\n",
    "\n",
    "    print(\"Solve status: %s\" % solver.StatusName(status))\n",
    "    print(\"Optimal objective value: %i\" % solver.ObjectiveValue())\n",
    "    print(\"Statistics\")\n",
    "    print(\"  - conflicts : %i\" % solver.NumConflicts())\n",
    "    print(\"  - branches  : %i\" % solver.NumBranches())\n",
    "    print(\"  - wall time : %f s\" % solver.WallTime())\n",
    "\n",
    "\n",
    "flexible_jobshop()\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 5
}
